﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0042_Connect : IAlgorithm
    {
        // 116. 填充每个节点的下一个右侧节点指针

        // 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。
        // 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
        // 初始状态下，所有 next 指针都被设置为 NULL。

        // 进阶：
        //  你只能使用常量级额外空间。
        //  使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

        // 提示：
        //  树中节点的数量少于 4096
        //  -1000 <= node.val <= 1000

        public void Test()
        {
            // 算法参数定义
            var tree = new Node(1)
            {
                left = new Node(2)
                {
                    left = new Node(4),
                    right = new Node(5)
                },
                right = new Node(3)
                {
                    left = new Node(6),
                    right = new Node(7)
                },
            };
            // 算法执行与打印
            Console.WriteLine(Connect(tree));
        }

        // 算法
        // DFS遍历
        public Node Connect(Node root)
        {
            if (root == null)
                return root;
            var queue = new Queue<Node>();
            queue.Enqueue(root);
            while (queue.Count > 0)
            {
                var size = queue.Count;
                for (int i = 0; i < size; i++)
                {
                    var tempNode = queue.Dequeue();
                    if (i < size - 1)
                        tempNode.next = queue.Peek();
                    if (tempNode.left != null)
                        queue.Enqueue(tempNode.left);
                    if (tempNode.right != null)
                        queue.Enqueue(tempNode.right);
                }
            }
            return root;
        }

        // 进阶，空间负责度为常量
        public Node Connect1(Node root)
        {
            if (root == null)
                return root;
            // 从根节点开始
            Node leftmost = root;
            while (leftmost.left != null)
            {
                // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
                Node head = leftmost;
                while (head != null)
                {
                    // CONNECTION 1
                    head.left.next = head.right;
                    // CONNECTION 2
                    if (head.next != null)
                        head.right.next = head.next.left;
                    // 指针向后移动
                    head = head.next;
                }
                // 去下一层的最左的节点
                leftmost = leftmost.left;
            }
            return root;
        }
    }
}
